package com.algorithm.sort.heap;

import java.util.PriorityQueue;

/**
 * leetcode-295:查找数据流的中位数
 * 1. 采用两个堆实现
 * 2. 大顶堆存放[0,n/2]的数据，小顶堆存放[n/2+1, n]的元素
 * 3. 如果新加入的数据小于等于大顶堆最大值，加入到最大堆；并将最大堆最大值移到小顶堆；
 * 4. 如果新加入的数据大于等于小顶堆的最小值，加入到小顶堆；并将小顶堆的最小值移到大顶堆；
 * 5. 中位数为大顶堆的最大值
 *
 * @program: sudy
 * @className: MedianFinder
 * @description: TODO
 * @author: kukuxiahuni
 * @create: 2020-02-05 19:50
 **/
public class MedianFinder {

    public static void main(String[] args) {
        MedianFinder medianFinder = new MedianFinder();
        medianFinder.addNum(-1);
        medianFinder.addNum(-2);
        medianFinder.addNum(-3);
//        medianFinder.addNum(4);
//        medianFinder.addNum(6);

//        medianFinder.minHeap.add(1);
//        medianFinder.minHeap.add(2);
//        medianFinder.minHeap.add(3);
//        System.out.println(medianFinder.minHeap.peek());
//        medianFinder.maxHeap.add(1);
//        medianFinder.maxHeap.add(2);
//        medianFinder.maxHeap.add(3);
//        System.out.println(medianFinder.maxHeap.peek());
//        System.out.println(medianFinder.findMedian());
        System.out.println(medianFinder.findMedian());
    }


    /**
     * 大顶堆
     */
    private final PriorityQueue<Integer> maxHeap = new PriorityQueue<>((p, q) -> {
        if (p > q) {
            return -1;
        } else if (p < q) {
            return 1;
        } else {
            return 0;
        }
    });
    /**
     * 小顶堆
     * 默认为小顶堆
     */
    private final PriorityQueue<Integer> minHeap = new PriorityQueue<>();

    public MedianFinder() {

    }

    /**
     * 添加元素
     *
     * @method:
     * @param:
     * @return:
     * @author: kukuxiahuni
     * @create: 2020/2/5 21:01
     * @modify_user:TODO
     * @modify_time: 2020/2/5 21:01
     **/
    public void addNum(int num) {
        maxHeap.add(num);
        minHeap.add(maxHeap.poll());
        if (maxHeap.size() < minHeap.size()) {
            maxHeap.add(minHeap.poll());
        }

    }

    public double findMedian() {
        if (maxHeap.size() == minHeap.size()) {
            return (minHeap.peek() + maxHeap.peek()) / 2.0;
        } else {

            return maxHeap.peek();
        }
    }

}
